/**
 * @author ChaP
 * @date 2019/05/16
 * @describe:
 */
package CodingTest.AC20190516;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode - 438
 * 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

 说明：

 字母异位词指字母相同，但排列不同的字符串。
 不考虑答案输出的顺序。
 示例 1:

 输入:
 s: "cbaebabacd" p: "abc"

 输出:
 [0, 6]

 解释:
 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
 */
public class findAnagrams {
    public List<Integer> findAnagrams(String s, String p){
        List<Integer> res = new ArrayList<Integer>();
        int slen = s.length();
        int plen = p.length();
        int[] r = new int[26];
        for(int k = 0;k<p.length();k++){
            r[p.charAt(k) - 'a'] ++;
        }
        for(int i = 0;i<slen-plen+1;i++){
            boolean falg = true;
            int[] a = new int[26];
            for(int j =i;j<i+plen;j++){
                a[s.charAt(j)-'a']++;
            }
            for(int h = 0;h<26;h++){
                if(r[h] != a[h]){
                    falg = false;
                    break;
                }
            }
            if(falg == true){res.add(i);}
        }
        return res;
    }

    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        findAnagrams fa = new findAnagrams();
        System.out.println(fa.findAnagrams(s,p));
    }
}
